package features.advance.leetcode.tree.easy;


import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author LIN
 * @date 2023-09-10 22:51
 *  617. 合并二叉树
 * 简单
 * 给你两棵二叉树： root1 和 root2 。
 *
 * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
 * 合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
 *
 * 返回合并后的二叉树。
 *
 * 注意: 合并过程必须从两个树的根节点开始。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
 * 输出：[3,4,5,5,4,null,7]
 * 示例 2：
 *
 * 输入：root1 = [1], root2 = [1,2]
 * 输出：[2,2]
 *
 *
 * 提示：
 *
 * 两棵树中的节点数目在范围 [0, 2000] 内
 * -104 <= Node.val <= 104
 */
public class Solution617 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public TreeNode<Integer> mergeTrees(TreeNode<Integer> t1, TreeNode<Integer> t2) {
                if (t1 == null) {
                    return t2;
                }
                if (t2 == null) {
                    return t1;
                }
                TreeNode merged = new TreeNode(t1.val + t2.val);
                Queue<TreeNode> queue = new LinkedList<TreeNode>();
                Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
                Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
                queue.offer(merged);
                queue1.offer(t1);
                queue2.offer(t2);
                while (!queue1.isEmpty() && !queue2.isEmpty()) {
                    TreeNode<Integer> node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
                    TreeNode<Integer> left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
                    if (left1 != null || left2 != null) {
                        if (left1 != null && left2 != null) {
                            TreeNode<Integer> left = new TreeNode(left1.val + left2.val);
                            node.left = left;
                            queue.offer(left);
                            queue1.offer(left1);
                            queue2.offer(left2);
                        } else if (left1 != null) {
                            node.left = left1;
                        } else if (left2 != null) {
                            node.left = left2;
                        }
                    }
                    if (right1 != null || right2 != null) {
                        if (right1 != null && right2 != null) {
                            TreeNode right = new TreeNode(right1.val + right2.val);
                            node.right = right;
                            queue.offer(right);
                            queue1.offer(right1);
                            queue2.offer(right2);
                        } else if (right1 != null) {
                            node.right = right1;
                        } else {
                            node.right = right2;
                        }
                    }
                }
                return merged;

            }
        };
        TreeNode<Integer> treeNode1 = TreeUtil.stringToTreeNode("[1,3,2,5]");
        TreeNode<Integer> treeNode2 = TreeUtil.stringToTreeNode("[2,1,3,null,4,null,7]");
        System.out.println(treeNode1);

    }

    static class Solution {
        public TreeNode<Integer> mergeTrees(TreeNode<Integer> t1, TreeNode<Integer> t2) {
            if (t1 == null) {
                return t2;
            }
            if (t2 == null) {
                return t1;
            }
            TreeNode merged = new TreeNode(t1.val + t2.val);
            merged.left = mergeTrees(t1.left, t2.left);
            merged.right = mergeTrees(t1.right, t2.right);
            return merged;
        }
    }
}
